#include <iostream>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;

typedef pair<int, int> PII;
const int N = 1e4 + 10, M = 2e4 + 10, K = 110, INF = 0x3f3f3f3f;

int n, m, k;
int h[N], e[M], w[M], ne[M], id;
int dist[N][K];
bool st[N][K];

void add(int a, int b, int c)
{
	id++;
	e[id] = b; ne[id] = h[a]; w[id] = c; h[a] = id; 
}

void dijkstra()
{
	memset(dist, 0x3f, sizeof dist);
	priority_queue<PII, vector<PII>, greater<PII>> heap;
	heap.push({0, 1});
	dist[1][0] = 0;
	
	while(heap.size())
	{
		auto tmp = heap.top(); heap.pop();
		int x = tmp.second, t = tmp.first;
		
		if(st[x][t % k]) continue;
		st[x][t % k] = true;
		
		for(int i = h[x]; i; i = ne[i])
		{
			int y = e[i], z = w[i];
			
			int p = t;
			if(t < z) p += (z - p + k - 1) / k * k;
			
			if(p + 1 < dist[y][(p + 1) % k])
			{
				dist[y][(p + 1) % k] = p + 1;
				heap.push({p + 1, y});
			 } 
		}
	}
}

int main()
{
	cin >> n >> m >> k;
	for(int i = 1; i <= m; i++)
	{
		int a, b, c; cin >> a >> b >> c;
		add(a, b, c);
	}
	
	dijkstra();
	
	if(dist[n][0] == INF) cout << -1 << endl;
	else cout << dist[n][0] << endl;
	
	return 0;
}














